#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
    const int INF=INT_MAX/2;
    int numberOfSets(int n, int maxDistance, vector<vector<int>>& roads) {
        vector<vector<int>> g(n,vector<int>(n,INF));
        for(auto& e:roads)
        {
            int x=e[0],y=e[1],w=e[2];
            g[x][y]=min(g[x][y],w);
            g[y][x]=min(g[y][x],w);
        }
        vector<vector<int>> f(n,vector<int>(n,INF));
        auto check=[&](int s)->bool
        {
            for(int i=0;i<n;i++)
            {
                if((s>>i)&1)
                    f[i]=g[i];
            }
            for(int k=0;k<n;k++)
            {
                if(((s>>k)&1)==0) continue;
                for(int i=0;i<n;i++)
                {
                    if(((s>>i)&1)==0) continue;
                    for(int j=0;j<n;j++)
                    {
                        if(((s>>j)&1)==0) continue;
                        f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
                    }
                }
            }
            for(int i=0;i<n;i++)
            {
                if(((s>>i)&1)==0) continue;
                for(int j=0;j<i;j++)
                {
                    if(((s>>j)&1)==0) continue;
                    if(f[i][j]>maxDistance) return false;
                }
            }
            return true;
        };
        int ans=0;
        for(int s=0;s<(1<<n);++s)
        {
            ans+=check(s);
        }
        return ans;
    }
};